{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of People That Can Be Seen in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #matrix #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #矩阵 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: seePeople"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在一个网格中可以看到的人数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <code>m x n</code> <strong>下标从 0 开始</strong>的二维正整数数组 <code>heights</code>，其中 <code>heights[i][j]</code> 是站在位置 <code>(i, j)</code>&nbsp;上的人的高度。</p>\n",
    "\n",
    "<p>站在 <code>(row<sub>1</sub>, col<sub>1</sub>)</code>&nbsp;位置的人可以看到站在 <code>(row<sub>2</sub>, col<sub>2</sub>)</code> 位置的人，前提是:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>(row<sub>2</sub>, col<sub>2</sub>)</code>&nbsp;的人在&nbsp;<code>(row<sub>1</sub>, col<sub>1</sub>)</code> 的人的右边&nbsp;<strong>或&nbsp;</strong>下面。更正式地说，要么 <code>row<sub>1</sub> == row<sub>2</sub></code>&nbsp;时&nbsp;<code>col<sub>1</sub> &lt; col<sub>2</sub></code>，要么&nbsp;<code>row<sub>1</sub> &lt; row<sub>2</sub></code><sub>&nbsp;</sub>时 <code>col<sub>1</sub> == col<sub>2</sub></code>。</li>\n",
    "\t<li>他们中间的人&nbsp;<strong>都&nbsp;</strong>比他们两个矮。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em>一个&nbsp;<code>m x n</code> 的二维整数数组<code>answer</code>，其中&nbsp;<code>answer[i][j]</code>&nbsp;是位于&nbsp;<code>(i, j)</code> 位置的人可以看到的人数。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/05/24/image-20220524180458-1.png\" style=\"width: 700px; height: 164px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> heights = [[3,1,4,2,5]]\n",
    "<strong>输出:</strong> [[2,1,2,1,0]]\n",
    "<strong>解释:</strong>\n",
    "- (0,0) 上的人可以看到 (0,1) 和 (0,2) 的人。\n",
    "  注意，他看不到 (0,4) 上的人，因为 (0,2) 上的人比他高。\n",
    "- (0,1) 上的人可以看到 (0,2) 上的人。\n",
    "- (0,2) 上的人可以看到 (0,3) 和 (0,4) 的人。\n",
    "- (0,3) 上的人可以看到 (0,4) 上的人。\n",
    "- (0,4) 上的人看不到任何人。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/05/23/image-20220523113533-2.png\" style=\"width: 400px; height: 249px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> heights = [[5,1],[3,1],[4,1]]\n",
    "<strong>输出:</strong> [[3,1],[2,1],[1,0]]\n",
    "<strong>解释:</strong>\n",
    "- (0,0) 上的人可以看到 (0,1)、(1,0) 和 (2,0) 的人。\n",
    "- (0,1) 上的人可以看到 (1,1) 上的人。\n",
    "- (1,0) 上的人可以看到 (1,1) 和 (2,0) 的人。\n",
    "- (1,1) 上的人可以看到 (2,1) 上的人。\n",
    "- (2,0) 上的人可以看到 (2,1) 上的人。\n",
    "- (2,1) 上的人看不到任何人。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= heights.length &lt;= 400</code></li>\n",
    "\t<li><code>1 &lt;= heights[i].length &lt;= 400</code></li>\n",
    "\t<li><code>1 &lt;= heights[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-people-that-can-be-seen-in-a-grid](https://leetcode.cn/problems/number-of-people-that-can-be-seen-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-people-that-can-be-seen-in-a-grid](https://leetcode.cn/problems/number-of-people-that-can-be-seen-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,1,4,2,5]]', '[[5,1],[3,1],[4,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            st = []\n",
    "            for j in range(n):\n",
    "                eq = False\n",
    "                while st and heights[i][st[-1]] <= heights[i][j]:\n",
    "                    if heights[i][st[-1]] == heights[i][j]:\n",
    "                        eq = True\n",
    "                    res[i][st.pop()] += 1\n",
    "                if st and not eq:\n",
    "                    res[i][st[-1]] += 1\n",
    "                st.append(j)\n",
    "        for j in range(n):\n",
    "            st = []\n",
    "            for i in range(m):\n",
    "                eq = False\n",
    "                while st and heights[st[-1]][j] <= heights[i][j]:\n",
    "                    if heights[st[-1]][j] == heights[i][j]:\n",
    "                        eq = True\n",
    "                    res[st.pop()][j] += 1\n",
    "                if st and not eq:\n",
    "                    res[st[-1]][j] += 1\n",
    "                st.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(heights)\n",
    "        n=len(heights[0])\n",
    "        ans=[[0]*n for i in range(m)]\n",
    "        stack=[]\n",
    "        for x in range(m):\n",
    "            stack.clear()\n",
    "            for y in range(n-1,-1,-1):\n",
    "                f=0\n",
    "               # print(stack)\n",
    "                while stack and stack[-1]<=heights[x][y]:\n",
    "                    if stack[-1]==heights[x][y]:\n",
    "                        f=1\n",
    "                        stack.pop()\n",
    "                    elif stack[-1]<heights[x][y]:\n",
    "                        stack.pop()\n",
    "                        ans[x][y]+=1\n",
    "                if stack or f==1:\n",
    "                    ans[x][y]+=1\n",
    "                stack.append(heights[x][y])\n",
    "\n",
    "        for y in range(n):\n",
    "            stack.clear()\n",
    "            for x in range(m-1,-1,-1):\n",
    "                f=0\n",
    "                while stack and stack[-1]<=heights[x][y]:\n",
    "                    if stack[-1]==heights[x][y]:\n",
    "                        f=1\n",
    "                        stack.pop()\n",
    "                    elif stack[-1]<heights[x][y]:\n",
    "                        stack.pop()\n",
    "                        ans[x][y]+=1\n",
    "                if stack or f==1:\n",
    "                    ans[x][y]+=1\n",
    "                stack.append(heights[x][y])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 单调栈\n",
    "    # 读题 - 他们中间的人都比他们两个矮\n",
    "    # 有 m x n 个人排成一个2维数组，一个人能【看到】他右边或下边的另一个人的条件是这两人之间的所有人都比他们两人矮 。更正式的，位置为(row1, col1)的人能看到(row2, col2)人的条件是row1 == row2 and col1 < col2 或者 row1 < row2 and col1 == col2，且二人之间的所有人的高度都小于二人的高度。请你返回一个m x n 的2维数组 answer ，其中 answer[i][j] 是位置为(i, j)的能【看到】的人数\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            stack = [heights[i][n-1]]\n",
    "            for j in range(n-2, -1, -1):\n",
    "                v = heights[i][j]\n",
    "                while stack and v > stack[-1]:\n",
    "                    res[i][j] += 1\n",
    "                    stack.pop()\n",
    "\n",
    "                if stack:\n",
    "                    res[i][j] += 1\n",
    "\n",
    "                if not stack or stack[-1] > v:\n",
    "                    stack.append(v)\n",
    "\n",
    "        for j in range(n):\n",
    "            stack = [heights[m-1][j]]\n",
    "            for i in range(m-2, -1, -1):\n",
    "                v = heights[i][j]\n",
    "                while stack and v > stack[-1]:\n",
    "                    res[i][j] += 1\n",
    "                    stack.pop()\n",
    "\n",
    "                if stack:\n",
    "                    res[i][j] += 1\n",
    "\n",
    "                if not stack or stack[-1] > v:\n",
    "                    stack.append(v)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 单调栈\n",
    "def canSeePersonsCount(heights: List[int]) -> List[int]:\n",
    "    res = [0] * len(heights)\n",
    "    stack = []\n",
    "    for i in range(len(heights) - 1, -1, -1):\n",
    "        while stack and stack[-1] < heights[i]:  # 必须要严格小于才不会被挡住\n",
    "            res[i] += 1\n",
    "            stack.pop()\n",
    "\n",
    "        if stack:\n",
    "            res[i] += 1\n",
    "\n",
    "        while stack and stack[-1] == heights[i]:  # 相等的全部出栈\n",
    "            stack.pop()\n",
    "\n",
    "        stack.append(heights[i])\n",
    "\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for r, row in enumerate(matrix):\n",
    "            cur = canSeePersonsCount(row)\n",
    "            for c, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        for c, col in enumerate(zip(*matrix)):\n",
    "            cur = canSeePersonsCount(list(col))\n",
    "            for r, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        def cansee(ls):\n",
    "            n=len(ls)\n",
    "            ret=[0]*n\n",
    "            q=[]\n",
    "            for i in range(n-1,-1,-1):\n",
    "                while q and q[-1]<ls[i]:\n",
    "                    q.pop()\n",
    "                    ret[i]+=1\n",
    "                if q:\n",
    "                    ret[i]+=1\n",
    "                while q and q[-1]==ls[i]:\n",
    "                    q.pop()\n",
    "                q.append(ls[i])\n",
    "            return ret\n",
    "        m,n=len(heights),len(heights[0])\n",
    "        ans=[[0 for _ in range(n)]for _ in range(m)]\n",
    "        for i,row in enumerate(heights):\n",
    "            cur=cansee(row)\n",
    "            for j,num in enumerate(cur):\n",
    "                ans[i][j]+=num\n",
    "        for j,col in enumerate(zip(*heights)):\n",
    "            cur=cansee(list(col))\n",
    "            for i,num in enumerate(cur):\n",
    "                ans[i][j]+=num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(heights),len(heights[0])\n",
    "        def find_look_nums(x,y)->int:\n",
    "            num=0\n",
    "            # 向下看\n",
    "            lst=0\n",
    "            for i in range(x+1,m):\n",
    "                if heights[i][y]>lst:\n",
    "                    lst=heights[i][y]\n",
    "                    num+=1\n",
    "                    if lst>=heights[x][y]:\n",
    "                        break\n",
    "            # 向右看\n",
    "            lst=0\n",
    "            for j in range(y+1,n):\n",
    "                if heights[x][j]>lst:\n",
    "                    lst=heights[x][j]\n",
    "                    num+=1\n",
    "                    if lst>=heights[x][y]:\n",
    "                        break\n",
    "            return num \n",
    "\n",
    "        ans=[]\n",
    "        for a in range(m):\n",
    "            tmp=[]\n",
    "            for b in range(n):\n",
    "                tmp.append(find_look_nums(a,b))\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(heights)\n",
    "        n=len(heights[0])\n",
    "        ans=[[0]*n for i in range(m)]\n",
    "        stack=[]\n",
    "        for x in range(m):\n",
    "            stack.clear()\n",
    "            for y in range(n-1,-1,-1):\n",
    "                f=0\n",
    "                while stack and stack[-1]<=heights[x][y]:\n",
    "                    if stack[-1]< heights[x][y]:\n",
    "                        ans[x][y]+=1\n",
    "                    else:\n",
    "                        f=1\n",
    "                    stack.pop()\n",
    "                if stack or f==1:\n",
    "                   ans[x][y]+=1\n",
    "                stack.append(heights[x][y])\n",
    "\n",
    "        for y in range(n):\n",
    "            stack.clear()\n",
    "            for x in range(m-1,-1,-1):\n",
    "                f=0\n",
    "                while stack and stack[-1]<=heights[x][y]:\n",
    "                    if stack[-1]< heights[x][y]:\n",
    "                        ans[x][y]+=1\n",
    "                    else:\n",
    "                        f=1\n",
    "                    stack.pop()\n",
    "                if stack or f==1:\n",
    "                    ans[x][y]+=1\n",
    "                stack.append(heights[x][y])\n",
    "    \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def canSeePersonsCount(heights: List[int]) -> List[int]:\n",
    "    res = [0] * len(heights)\n",
    "    stack = []\n",
    "    for i in range(len(heights) - 1, -1, -1):\n",
    "        while stack and stack[-1] < heights[i]:  # 必须要严格小于才不会被挡住\n",
    "            res[i] += 1\n",
    "            stack.pop()\n",
    "        if stack:\n",
    "            res[i] += 1\n",
    "        while stack and stack[-1] == heights[i]:  # 相等的全部出栈\n",
    "            stack.pop()\n",
    "        stack.append(heights[i])\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for r, row in enumerate(matrix):\n",
    "            cur = canSeePersonsCount(row)\n",
    "            for c, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        for c, col in enumerate(zip(*matrix)):\n",
    "            cur = canSeePersonsCount(list(col))\n",
    "            for r, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(heights), len(heights[0])\n",
    "        ans = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        stack = []\n",
    "        \n",
    "        # 遍历每一行\n",
    "        for i in range(n):\n",
    "            stack.clear()\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                flag = 0\n",
    "                while stack and stack[-1] <= heights[i][j]:\n",
    "                    if stack[-1] < heights[i][j]:\n",
    "                        ans[i][j] += 1\n",
    "                    else:\n",
    "                        flag = 1\n",
    "                    stack.pop()\n",
    "                if stack or flag:\n",
    "                    ans[i][j] += 1\n",
    "                stack.append(heights[i][j])\n",
    "        \n",
    "        # 遍历每一列\n",
    "        for j in range(m):\n",
    "            stack.clear()\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                flag = 0\n",
    "                while stack and stack[-1] <= heights[i][j]:\n",
    "                    if stack[-1] < heights[i][j]:\n",
    "                        ans[i][j] += 1\n",
    "                    else:\n",
    "                        flag = 1\n",
    "                    stack.pop()\n",
    "                if stack or flag:\n",
    "                    ans[i][j] += 1\n",
    "                stack.append(heights[i][j])\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            stark = [heights[i][n-1]]\n",
    "            for j in range(n-2,-1,-1):\n",
    "                v = heights[i][j]\n",
    "                while stark and v > stark[-1]:\n",
    "                    res[i][j] += 1\n",
    "                    stark.pop()\n",
    "                if stark: res[i][j] += 1\n",
    "                if not stark or stark[-1] > v: stark.append(v)\n",
    "        for j in range(n):\n",
    "            stark = [heights[m-1][j]]\n",
    "            for i in range(m-2,-1,-1):\n",
    "                v = heights[i][j]\n",
    "                while stark and v > stark[-1]:\n",
    "                    res[i][j] += 1\n",
    "                    stark.pop()\n",
    "                if stark: res[i][j] += 1\n",
    "                if not stark or stark[-1] > v: stark.append(v)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            stack = [heights[i][n-1]]\n",
    "            for j in range(n-2,-1,-1):\n",
    "                v = heights[i][j]\n",
    "                while stack and v > stack[-1]:\n",
    "                    res[i][j] += 1\n",
    "                    stack.pop()\n",
    "\n",
    "                if stack: res[i][j] += 1\n",
    "                if not stack or stack[-1] > v: stack.append(v)\n",
    "\n",
    "        for j in range(n):\n",
    "            stack = [heights[m-1][j]]\n",
    "            for i in range(m-2,-1,-1):\n",
    "                v = heights[i][j]\n",
    "                while stack and v > stack[-1]:\n",
    "                    res[i][j] += 1\n",
    "                    stack.pop()\n",
    "\n",
    "                if stack: res[i][j] += 1\n",
    "                if not stack or stack[-1] > v: stack.append(v)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        def f(nums: List[int]) -> List[int]:\n",
    "            n = len(nums)\n",
    "            stk = []\n",
    "            ans = [0] * n\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                while stk and stk[-1] < nums[i]:\n",
    "                    ans[i] += 1\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    ans[i] += 1\n",
    "                while stk and stk[-1] == nums[i]:\n",
    "                    stk.pop()\n",
    "                stk.append(nums[i])\n",
    "            return ans\n",
    "\n",
    "        ans = [f(row) for row in heights]\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        for j in range(n):\n",
    "            add = f([heights[i][j] for i in range(m)])\n",
    "            for i in range(m):\n",
    "                ans[i][j] += add[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def canSeePersonsCount(x: int,heights: List[int]) -> List[int]:\n",
    "    res = [0 for _ in range(x)]\n",
    "    stack = []\n",
    "    for i in range(x - 1, -1, -1):\n",
    "        while stack and stack[-1] < heights[i]:  # 必须要严格小于才不会被挡住\n",
    "            res[i] += 1\n",
    "            stack.pop()\n",
    "        if stack:\n",
    "            res[i] += 1\n",
    "        while stack and stack[-1] == heights[i]:  # 相等的全部出栈\n",
    "            stack.pop()\n",
    "        stack.append(heights[i])\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for r, row in enumerate(matrix):\n",
    "            cur = canSeePersonsCount(n, row)\n",
    "            for c, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        for c, col in enumerate(zip(*matrix)):\n",
    "            cur = canSeePersonsCount(m, list(col))\n",
    "            for r, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(heights), len(heights[0])\n",
    "        ans = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        stack = []\n",
    "        \n",
    "        # 遍历每一行\n",
    "        for i in range(n):\n",
    "            stack.clear()\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                flag = 0\n",
    "                while stack and stack[-1] <= heights[i][j]:\n",
    "                    if stack[-1] < heights[i][j]:\n",
    "                        ans[i][j] += 1\n",
    "                    else:\n",
    "                        flag = 1\n",
    "                    stack.pop()\n",
    "                if stack or flag:\n",
    "                    ans[i][j] += 1\n",
    "                stack.append(heights[i][j])\n",
    "        \n",
    "        # 遍历每一列\n",
    "        for j in range(m):\n",
    "            stack.clear()\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                flag = 0\n",
    "                while stack and stack[-1] <= heights[i][j]:\n",
    "                    if stack[-1] < heights[i][j]:\n",
    "                        ans[i][j] += 1\n",
    "                    else:\n",
    "                        flag = 1\n",
    "                    stack.pop()\n",
    "                if stack or flag:\n",
    "                    ans[i][j] += 1\n",
    "                stack.append(heights[i][j])\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(heights), len(heights[0])\n",
    "        res=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dq=deque()\n",
    "            for j in range(n-1, -1, -1):\n",
    "                while dq and dq[-1] < heights[i][j]:\n",
    "                    res[i][j]+=1\n",
    "                    dq.pop()\n",
    "                if dq:\n",
    "                    res[i][j]+=1\n",
    "                while dq and dq[-1] == heights[i][j]:\n",
    "                    dq.pop()\n",
    "                dq.append(heights[i][j])\n",
    "        for j in range(n):\n",
    "            dq=deque()\n",
    "            for i in range(m-1, -1, -1):\n",
    "                while dq and dq[-1] < heights[i][j]:\n",
    "                    res[i][j]+=1\n",
    "                    dq.pop()\n",
    "                if dq:\n",
    "                    res[i][j]+=1\n",
    "                while dq and dq[-1] == heights[i][j]:\n",
    "                    dq.pop()\n",
    "                dq.append(heights[i][j])       \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(heights)\n",
    "        n=len(heights[0])\n",
    "        ans=[[0]*n for i in range(m)]\n",
    "        stack=[]\n",
    "        for i in range(m):\n",
    "            stack=[]\n",
    "            for j  in range(n-1,-1,-1):\n",
    "                f=0\n",
    "                while stack and heights[i][stack[-1]]<=heights[i][j]:\n",
    "                    t=heights[i][j]\n",
    "                    if t==heights[i][stack[-1]]:\n",
    "                        stack.pop()\n",
    "                        f=1\n",
    "                    elif t>heights[i][stack[-1]]:\n",
    "                        ans[i][j]+=1\n",
    "                        stack.pop()\n",
    "                if len(stack) or f==1:\n",
    "                    ans[i][j]+=1\n",
    "                stack.append(j)\n",
    "\n",
    "        print(ans)\n",
    "        for j in range(n):\n",
    "            stack=[]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                f=0\n",
    "                while stack and heights[stack[-1]][j]<=heights[i][j]:\n",
    "                    t=heights[i][j]\n",
    "                    if t==heights[stack[-1]][j]:\n",
    "                        f=1\n",
    "                        stack.pop()\n",
    "                    elif t>heights[stack[-1]][j]:\n",
    "                        ans[i][j]+=1\n",
    "                        stack.pop()\n",
    "                if len(stack) or f==1:\n",
    "                    ans[i][j]+=1\n",
    "                stack.append(i)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        \n",
    "        :param heights:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def get_mono_stack(ll):\n",
    "            st = []\n",
    "            ret = []\n",
    "            for k, v in enumerate(ll):\n",
    "                cnt = 0\n",
    "                picked = -1\n",
    "                added = False\n",
    "                for i in range(k + 1, len(ll)):\n",
    "                    if ll[i] >= v:\n",
    "                        cnt += 1\n",
    "                        ret.append(cnt)\n",
    "                        added = True\n",
    "                        break\n",
    "                    else:\n",
    "                        if ll[i] > picked:\n",
    "                            picked = ll[i]\n",
    "                            cnt += 1\n",
    "                if not added:\n",
    "                    ret.append(cnt)\n",
    "            return ret\n",
    "\n",
    "        ll1 = []\n",
    "        for i in heights:\n",
    "            ll1.append(get_mono_stack(i))\n",
    "\n",
    "        ll2 = []\n",
    "        for i in range(len(heights[0])):\n",
    "            x1 = []\n",
    "            for j in range(len(heights)):\n",
    "                x1.append(heights[j][i])\n",
    "            ll2.append(get_mono_stack(x1))\n",
    "\n",
    "        ret = []\n",
    "        for k, v in enumerate(heights):\n",
    "            ret1 = []\n",
    "            for k2, v2 in enumerate(v):\n",
    "                v1 = ll1[k][k2]\n",
    "                v2 = ll2[k2][k]\n",
    "                ret1.append(v1 + v2)\n",
    "            ret.append(ret1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.seePeople([[4, 2, 1, 1, 3]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        :param heights:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def get_mono_stack(ll):\n",
    "            ret = []\n",
    "            for k, v in enumerate(ll):\n",
    "                cnt = 0\n",
    "                picked = -1\n",
    "                added = False\n",
    "                for i in range(k + 1, len(ll)):\n",
    "                    if ll[i] >= v:\n",
    "                        cnt += 1\n",
    "                        ret.append(cnt)\n",
    "                        added = True\n",
    "                        break\n",
    "                    else:\n",
    "                        if ll[i] > picked:\n",
    "                            picked = ll[i]\n",
    "                            cnt += 1\n",
    "                if not added:\n",
    "                    ret.append(cnt)\n",
    "            return ret\n",
    "\n",
    "        ll1 = []\n",
    "        for i in heights:\n",
    "            ll1.append(get_mono_stack(i))\n",
    "\n",
    "        ll2 = []\n",
    "        for i in range(len(heights[0])):\n",
    "            x1 = []\n",
    "            for j in range(len(heights)):\n",
    "                x1.append(heights[j][i])\n",
    "            ll2.append(get_mono_stack(x1))\n",
    "\n",
    "        ret = []\n",
    "        for k, v in enumerate(heights):\n",
    "            ret1 = []\n",
    "            for k2, v2 in enumerate(v):\n",
    "                v1 = ll1[k][k2]\n",
    "                v2 = ll2[k2][k]\n",
    "                ret1.append(v1 + v2)\n",
    "            ret.append(ret1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.seePeople([[4, 2, 1, 1, 3]]))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
